package com.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * 417. 太平洋大西洋水流问题
 * 深度优先搜索
 * 2022-04-27-每日一题
 *
 * @author fy
 * @date 2022/4/27 11:48
 */
public class Solution417_1 {

    // 方向: 下, 上, 左, 右
    private static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int[][] heights;
    private int m;
    private int n;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        this.heights = heights;
        this.m = heights.length;
        this.n = heights[0].length;

        // 下标对应点 是否能流到太平洋, 大西洋
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];

        // 遍历四个方向
        for (int i = 0; i < m; i++) {
            bfs(i, 0, pacific);
        }
        for (int j = 1; j < n; j++) {
            bfs(0, j, pacific);
        }
        for (int i = 0; i < m; i++) {
            bfs(i, n - 1, atlantic);
        }
        for (int j = 0; j < n - 1; j++) {
            bfs(m - 1, j, atlantic);
        }
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    List<Integer> cell = new ArrayList<>();
                    cell.add(i);
                    cell.add(j);
                    result.add(cell);
                }
            }
        }
        return result;
    }

    private void bfs(int row, int col, boolean[][] ocean) {
        // 已经流到了的就不用再次重复遍历了
        if (ocean[row][col]) {
            return;
        }
        // 默认靠海的都能流到, 并且识为true,不需要重复遍历
        ocean[row][col] = true;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{row, col});
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] dir : dirs) {
                int newRow = cell[0] + dir[0];
                int newCol = cell[1] + dir[1];
                // 在区域内, 并且高度更高, 并且没有访问过. 不然重复遍历会内存溢出
                if (inArea(newRow, newCol)
                        && this.heights[cell[0]][cell[1]] <= this.heights[newRow][newCol]
                        && !ocean[newRow][newCol]) {
                    ocean[newRow][newCol] = true;
                    queue.offer(new int[]{newRow, newCol});
                }
            }
        }
    }

    private boolean inArea(int row, int col) {
        return row >= 0 && row < this.m && col >= 0 && col < this.n;
    }


    public static void main(String[] args) {
        int[][] heights = {{1, 2, 2, 3, 5}, {3, 2, 3, 4, 4}, {2, 4, 5, 3, 1}, {6, 7, 1, 4, 5}, {5, 1, 1, 2, 4}};
        List<List<Integer>> res = new Solution417_1().pacificAtlantic(heights);
        System.out.println(res);
    }

}
